package leetcode.editor.cn.q1xx

import kotlin.math.max

class Q122 {
    fun maxProfit(prices: IntArray): Int {
        val n = prices.size
        val dp = Array(n) { IntArray(2) }
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for (i in 1 until n) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            dp[i][1] = max(dp[i-1][0], dp[i-1][1] - prices[i])
        }
        return dp[n-1][0]
    }
}